package com.xcoder.leetcode;

import java.util.LinkedList;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 * <p>
 * 前缀表达式、中缀表达式、后缀表达式
 */
public class _150_逆波兰表达式求值_中等 {

    /**
     * 栈，可以存Integer！！ 开始没想到存了String。。
     */
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String item : tokens) {
            switch (item) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int plus = stack.pop();
                    stack.push(stack.pop() - plus);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int div = stack.pop();
                    stack.push(stack.pop() / div);
                    break;
                default:
                    stack.push(Integer.valueOf(item));
                    break;
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens1 = {"2", "1", "+", "3", "*"};
        System.out.println(evalRPN(tokens1));

        String[] tokens2 = {"4", "13", "5", "/", "+"};
        System.out.println(evalRPN(tokens2));

        String[] tokens3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
        System.out.println(evalRPN(tokens3));
    }
}
